package com.fw.leetcode.matrix;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 73. Set Matrix Zeroes
 *
 * Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.
 * You must do it in place.
 *
 * Example 1:
 *  Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
 *  Output: [[1,0,1],[0,0,0],[1,0,1]]
 *
 * Example 2:
 *  Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
 *  Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]
 *
 * Constraints:
 *  m == matrix.length
 *  n == matrix[0].length
 *  1 <= m, n <= 200
 *  -2^31 <= matrix[i][j] <= 2^31 - 1
 *
 * Follow up:
 *  A straightforward solution using O(mn) space is probably a bad idea.
 *  A simple improvement uses O(m + n) space, but still not the best solution.
 *  Could you devise a constant space solution?
 */
public class Num_0073 implements LeetCode {

    private interface Solution {
        void setZeroes(int[][] matrix);

        default void assertExpected(int[][] matrix, int[][] expected) {
            int[][] oldMatrix = new int[matrix.length][matrix[0].length];
            for (int i = 0; i < oldMatrix.length; i++) {
                System.arraycopy(matrix[i], 0, oldMatrix[i], 0, oldMatrix[i].length);
            }
            setZeroes(matrix);
            for (int i = 0; i < matrix.length; i++) {
                if (!Arrays.equals(matrix[i], expected[i])) {
                    setZeroes(oldMatrix);
                }
            }
        }
    }

    private static class First0RcMarkSolution implements Solution {

        @Override
        public void setZeroes(int[][] matrix) { // 最优，第0行列标记：时O(mn) 空O(1)
            /*
             * 用第一行第一列进行标记
             * - 是否第一行第一列存在0
             * - 用第一行记录每个列上是否有为0的元素，若有，标记为 0，否则不动
             * - 用第一列记录每个行上是否有为0的元素，若有，标记为 0，否则不动
             */
            // 1.第一行第一列是否存在0
            boolean row0 = false;
            boolean col0 = false;
            for (int i = 0; i < matrix.length; i++) { // 遍历列
                if (matrix[i][0] == 0) {
                    col0 = true;
                }
            }
            for (int j = 0; j < matrix[0].length; j++) { // 遍历行
                if (matrix[0][j] == 0) {
                    row0 = true;
                }
            }
            // 2.遍历其余行列，标记是否存在为0元素位置
            for (int i = 1; i < matrix.length; i++) {
                for (int j = 1; j < matrix[i].length; j++) {
                    if (matrix[i][j] == 0) { // 在标记行列中进行标记
                        matrix[0][j] = 0; // 存在为0的列
                        matrix[i][0] = 0; // 存在为0的行
                    }
                }
            }
            // 3.将需要刷0的行列置0
            for (int i = 1; i < matrix.length; i++) { // 遍历标记列
                if (matrix[i][0] == 0) {
                    Arrays.fill(matrix[i], 0); // 将为0行置0
                }
            }
            for (int j = 1; j < matrix[0].length; j++) { // 遍历标记行
                if (matrix[0][j] == 0) {
                    for (int i = 1; i < matrix.length; i++) {
                        matrix[i][j] = 0; // 将为0列置0
                    }
                }
            }
            // 4.最后将标记行列置0
            if (col0) {
                for (int i = 0; i < matrix.length; i++) { // 遍历列
                    matrix[i][0] = 0;
                }
            }
            if (row0) {
                for (int j = 0; j < matrix[0].length; j++) { // 遍历行
                    matrix[0][j] = 0;
                }
            }
        }
    }

    private static class Find1st0RcMarkSolution implements Solution {

        @Override
        public void setZeroes(int[][] matrix) { // 其次：寻找第一个为0的位置行列标记：时O(mn) 空O(1)，慢在第一步寻找上
            /*
             * 先找到一个为0的元素位置(c0i, c0j)，用其所在行列进行标记
             * - 用行c0i记录每个列上是否有为0的元素，若有，标记为 0，否则标记为 1
             * - 用列c0j记录每个行上是否有为0的元素，若有，标记为 0，否则标记为 1
             */
            // 1.寻找第一个为0元素位置
            int c0i = -1;
            int c0j = -1;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j] == 0) {
                        c0i = i;
                        c0j = j;
                        break;
                    }
                }
            }
            if (c0i == -1) {
                return;
            }
            // 2.遍历此元素所在列，标记是否存在为0元素位置
            for (int i = 0; i < matrix.length; i++) { // 遍历列
                if (matrix[i][c0j] != 0) {
                    matrix[i][c0j] = 1; // 标记不是0
                }
            }
            // 3.遍历此元素所在行，标记是否存在为0元素位置
            for (int j = 0; j < matrix[c0i].length; j++) { // 遍历行
                if (matrix[c0i][j] != 0) {
                    matrix[c0i][j] = 1; // 标记不是0
                }
            }
            // 4.遍历其余行列，标记是否存在为0元素位置
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    if (i == c0i || j == c0j) { // 跳过用于标记的行列
                        continue;
                    }
                    if (matrix[i][j] == 0) { // 在标记行列中进行标记
                        matrix[c0i][j] = 0; // 存在为0的列
                        matrix[i][c0j] = 0; // 存在为0的行
                    }
                }
            }
            // 5.将需要刷0的行列置0（除标记行列先不动）
            for (int i = 0; i < matrix.length; i++) { // 遍历标记列
                if (matrix[i][c0j] == 0 && i != c0i) {
                    Arrays.fill(matrix[i], 0); // 将为0行置0
                }
            }
            for (int j = 0; j < matrix[c0i].length; j++) { // 遍历标记行
                if (matrix[c0i][j] == 0 && j != c0j) {
                    for (int i = 0; i < matrix.length; i++) {
                        matrix[i][j] = 0; // 将为0列置0
                    }
                }
            }
            // 6.最后将标记行列置0
            for (int i = 0; i < matrix.length; i++) { // 遍历列
                matrix[i][c0j] = 0;
            }
            for (int j = 0; j < matrix[c0i].length; j++) { // 遍历行
                matrix[c0i][j] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new First0RcMarkSolution();
        solution.assertExpected(new int[][]{{1}}, new int[][]{{1}});
        solution.assertExpected(new int[][]{{1,0,3}}, new int[][]{{0,0,0}});
        solution.assertExpected(new int[][]{{1,1,1},{1,0,1},{1,1,1}}, new int[][]{{1,0,1},{0,0,0},{1,0,1}});
        solution.assertExpected(new int[][]{{0,1,2,0},{3,4,5,2},{1,3,1,5}}, new int[][]{{0,0,0,0},{0,4,5,0},{0,3,1,0}});
    }
}
